/*
 * $Id: Queue.h,v 1.2 2005-07-13 14:52:45 bacon Exp $
 */

#ifndef _XPP_BAS_QUEUE_CLASS_
#define _XPP_BAS_QUEUE_CLASS_

#include <xp/types.h>
#include <xp/macros.h>
#include <xpp/bas/Link.h>
#include <xpp/bas/MemoryPool.h>
#include <xpp/bas/MemoryPoolable.h>
#include <xp/bas/assert.h>

namespace xpp 
{
	namespace bas
	{
	
		template <typename T> class Queue;
		
		template <typename T>
		class QueueNode: protected Link, protected MemoryPoolable
		{
		public:
			friend class Queue<T>;

			T value;

			QueueNode<T>* forward () 
			{
				return (QueueNode<T>*)link;
			}
			const QueueNode<T>* forward () const
			{
				return (const QueueNode<T>*)link;
			}
		
		protected:
			QueueNode () {}
			QueueNode (const T& v): value(v) {}

			void set_forward (const QueueNode<T>* node)
			{
				link = (Link*)node;
			}
		};
		
		template <typename T> class Queue 
		{
		public:
			typedef QueueNode<T> Node;
		
			Queue (xp_size_t mpb_size = 0): mp (xp_sizeof(Node), mpb_size)
			{
				this->queue_size = 0;
				this->front_node = XP_NULL;
				this->back_node  = XP_NULL;
			}

			Queue (const Queue<T>& s): mp (s.mp.datumSize(), s.mp.blockSize())
			{
				front_node = XP_NULL;
				back_node  = XP_NULL;
				queue_size = 0;
		
				Node* n = s.front_node; 
				while (n != XP_NULL) {
					Node* node = new Node (n->node_value);
					if (queue_size == 0) {
						back_node = front_node = node;
					}
					else {
						back_node->forward() = node;
						back_node = node;	
					}
					queue_size++;
					n = n->forward();
				}
			}
			~Queue () 
			{
				clearout ();
			}
		
			Queue<T>& operator= (const Queue<T>& s) 
			{
				clear ();
		
				Node* n = s.front_node; 
				while (n != XP_NULL) {
					Node* node = new Node (n->node_value);
					if (queue_size == 0) {
						back_node = front_node = node;
					}
					else {
						back_node->forward() = node;
						back_node = node;	
					}
					queue_size++;
					n = n->forward();
				}
		
				return *this;
			}
		
			void push (const T& value) 
			{
				Node* n = mp.isEnabled()?
					(new(&mp) Node(value)): (new Node(value));

				if (queue_size == 0) {
					back_node = front_node = n;
				}		
				else {
					back_node->set_forward (n);
					back_node = n;
				}
				queue_size++;
			}
		
			void pop () 
			{
				xp_assert (queue_size > 0);
		
				if (queue_size == 1) {
					if (mp.isDisabled()) delete back_node;
					else {
						back_node->~Node ();
						back_node->dispose (back_node, &mp);
					}
					back_node = front_node = XP_NULL;
				}
				else {
					Node* p = front_node;
					front_node = front_node->forward();

					if (mp.isDisabled()) delete p;
					else {
						p->~Node ();
						p->dispose (p, &mp);
					}
				}
				queue_size--;
			}
		
			T& front ()
			{
				xp_assert (queue_size > 0);
				return front_node->value;
			}
			const T& front () const 
			{
				xp_assert (queue_size > 0);
				return front_node->value;
			}

			T& back ()
			{
				xp_assert (queue_size > 0);
				return back_node->node_value;
			}
			const T& back () const 
			{
				xp_assert (queue_size > 0);
				return back_node->node_value;
			}
		
			xp_size_t size () const 
			{
				return queue_size;
			}

			bool isEmpty () const
			{
				return queue_size == 0;
			}

			void clear () 
			{
				while (queue_size > 0) pop ();
			}

			void clearout ()
			{
				clear ();
				mp.dispose ();
			}
		
		protected:
			MemoryPool mp;
			Node*      front_node;
			Node*      back_node;
			xp_size_t  queue_size;
		};
		
	}
}
#endif
